Kraal-sorteeralgoritme in PHP
Home

Kraal-sorteeralgoritme in PHP

Kraal-sorteeralgoritme in PHP

In het Engels bead/gravity sort algoritm. Kraal verwijst naar kralen die je op een telraam of een abacus heen en weer kan schuiven in horizontale of verticale richting, om wiskundige berekeningen mee uit te voeren.

Gravity of zwaartekracht verwijst naar het effect van de zwaartekracht op de kralen op een vertikale staaf: ze vallen allemaal naar beneden.

De code hieronder is bedoeld om te leren werken met array's. Niet om een efficiënt sorteeralgoritme te maken!

Het idee erachter

Bead sort is een sorteeralgoritme aangedreven als het ware door zwaartekracht.

In het voorbeeld stellen we de getallen 7, 2, 1, 4 en 2 voor met kralen op een staven in een telraam:

bead-sort-concept-gravity
bead-sort-concept-gravity
  1. Elk getal x in de array dat we willen sorteren, stellen we voor als x kralen op een rij.
  2. Laat ze allemaal vallen.
  3. Tel het aantal kralen in elke rij van boven naar beneden, en we hebben onze gesorteerde reeks.

Video

De implementatie

Overzicht van de verschillende stappen:

bead-sort-php-overview
bead-sort-php-overview
  1. numbersToAbacus
    Een methode om de getallen als sterren op één rij in de abacus te zetten: 
    function numbersToAbacus($numbers)
{
    $maxNumber = max($numbers);
    // $row = str_repeat('_', $maxNumber);
    $abacus = array();
    foreach ($numbers as $number) {
        $abacus[] = str_repeat('*', $number) . str_repeat('_', $maxNumber - $number);
    }
    return $abacus;
}
  2. rotateAbacus
    Een methode om van de rijen kolommen te maken, of om kolommen in rijen te veranderen: 
    function rotateAbacus($abacus)
{
    $rotatedAbacus = array_fill(0, strlen($abacus[0]), str_repeat('=', count($abacus) - 1,));
    for ($i = 0; $i < count($abacus); $i++) {
        for ($j = 0; $j < strlen($abacus[$i]); $j++) {
            $rotatedAbacus[$j][$i] = $abacus[$i][$j];
        }
    }
    // var_dump($rotatedAbacus);
    return $rotatedAbacus;
}
  3. gravitateAbacus
    Een methode om de kralen naar links te laten vallen. Normaal gezien vallen dingen naar beneden, maar in een programma kunnen we dingen naar links laten vallen :) 
    function gravitateAbacus($abacus)
{
    $maxNumber = strlen($abacus[0]);
    for ($i = 0; $i < count($abacus); $i++) {
        $number = substr_count($abacus[$i], '*');
        $abacus[$i] = str_repeat('*', $number) . str_repeat('_', $maxNumber - $number);
    }
    return $abacus;
}

  4. rotateAbacus
    We gebruiken nog eens de methode rotateAbacus om de rijen weer om te zetten naar kolommen.

  5. abacusToNumbers Een methode om het aantal kralen per rij om te zetten naar een natuurlijk getal. Beginnen met de onderste rij uit het telraam: 
    function abacusToNumbers($abacus)
{
    $numbers = array();
    for ($i = count($abacus) - 1; $i >= 0; $i--) {
        $number = substr_count($abacus[$i], '*');
        $numbers[] = $number;
    }
    return $numbers;
}

Twee hulpfuncties, eentje om een array van integers af te printen en een andere om een rij van strings af te printen.

  1. echoArray 
    function echoArray($numbers)
{
    foreach ($numbers as $number) {
        echo "$number<br/>";
    }
}
  2. echoAbacus 
    function echoAbacus($abacus)
{
    foreach ($abacus as $row) {
        echo "$row<br/>";
    }
}

Uitproberen

  1. Code

    Maak een bestand met de naam bead-sort.php met daarin:

    <?php

function numbersToAbacus($numbers)
{
    $maxNumber = max($numbers);
    // $row = str_repeat('_', $maxNumber);
    $abacus = array();
    foreach ($numbers as $number) {
        $abacus[] = str_repeat('*', $number) . str_repeat('_', $maxNumber - $number);
    }
    return $abacus;
}

function rotateAbacus($abacus)
{
    $rotatedAbacus = array_fill(0, strlen($abacus[0]), str_repeat('=', count($abacus) - 1,));
    for ($i = 0; $i < count($abacus); $i++) {
        for ($j = 0; $j < strlen($abacus[$i]); $j++) {
            $rotatedAbacus[$j][$i] = $abacus[$i][$j];
        }
    }
    // var_dump($rotatedAbacus);
    return $rotatedAbacus;
}

function echoAbacus($abacus)
{
    foreach ($abacus as $row) {
        echo "$row<br/>";
    }
}

function gravitateAbacus($abacus)
{
    $maxNumber = strlen($abacus[0]);
    for ($i = 0; $i < count($abacus); $i++) {
        $number = substr_count($abacus[$i], '*');
        $abacus[$i] = str_repeat('*', $number) . str_repeat('_', $maxNumber - $number);
    }
    return $abacus;
}

function abacusToNumbers($abacus)
{
    $numbers = array();
    for ($i = count($abacus) - 1; $i >= 0; $i--) {
        $number = substr_count($abacus[$i], '*');
        $numbers[] = $number;
    }
    return $numbers;
}

function echoArray($numbers)
{
    foreach ($numbers as $number) {
        echo "$number<br/>";
    }
}

$sampleNumbers = array(10, 5, 3, 8, 20, 7, 4, 1, 3, 12, 14, 6, 4, 1, 1);
$sampleAbacus = numbersToAbacus($sampleNumbers);
$rotatedAbacus = rotateAbacus($sampleAbacus);
$gravitatedAbacus = gravitateAbacus($rotatedAbacus);
$rotatedBackAbacus = rotateAbacus($gravitatedAbacus);
$sortedNumbers = abacusToNumbers($rotatedBackAbacus);

?>

<!doctype html>
<html lang="nl">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Bead sort algoritm</title>
    <style>
        body {
            display: flex;
            justify-content: space-around;
        }
    </style>
</head>
<body>
<p>
    <?php echoArray($sampleNumbers); ?>
</p>
<p>
    <?php echoAbacus($sampleAbacus); ?>
</p>
<p>
    <?php echoAbacus($rotatedAbacus); ?>
</p>
<p>
    <?php echoAbacus($gravitatedAbacus); ?>
</p>
<p>
    <?php echoAbacus($rotatedBackAbacus); ?>
</p>
<p>
    <?php echoArray($sortedNumbers); ?>
</p>
</body>
</html>
  2. Resultaat
    resultaat bead-sort
    resultaat bead-sort

JI
2021-02-27 16:27:00